Many search schemes and indexing approaches have been developed to manage file systems and/or databases. One example of an approach is a binary tree approach. In a binary tree approach, a node is established as the root node and the first node that has a greater value than the root node becomes the root node's right child node. Likewise, the first node with a value lower than the root node becomes the root node's left child node. A node that has a value greater than the root node, but less than the root node's right child node becomes the right child node's left child node. The tree structure is built this way as nodes are added to the tree. Periodically, the tree may be rebalanced to even the distribution of nodes from one side of the root node to the other. Ideally, the root node is the middle value of all nodes so that all searches take approximately the same amount of time to complete (i.e., so roughly half the searches traverse the left child node branch and half traverse the right child node branch). In an unbalanced tree, that is, where one node branch of the root node is significantly larger than the other node branch, search performance suffers because one branch of the search tree takes significantly longer to search through. After rebalancing the tree, neither side of the tree has generally more or less nodes than the other side.
Another approach to searching is the “B-Tree” approach. In a B-Tree, the nodes of the tree may have a larger number of data elements per node compared to the one data element of the binary tree. Correspondingly, a B-Tree may have a larger number of child nodes per parent node since the child nodes contain values between the parent node element values. Unlike the binary tree node which has one data element and two pointers, one for nodes greater than the current node and one for nodes less than the current node, the B-Tree node may have, for example, four data elements per node. The searched-for term is compared against the elements at the current node level, and if the searched-for term falls between nodes, a pointer for that gap is followed.
Using a B+-tree, or other variants, another approach caches portions of the index which are frequently accessed. For example, see US patent publication number 2003/0033328. The nodes that are cached and read are acquired from the database without a latch. There is a scheme described that uses a latch bit and a version number to ensure that the cached files are accurate and consistent. During the read operation, a version of the node is copied into a register. The contents of the node are read. A latch bit of the read node is examined to ensure that the node has not been latched by another process. The version number of the read node is compared to the version number in the register to ensure that the contents have not been updated during the read operation. If both the latch bit is not set and the version has not changed, then the node is in a consistent state and the node is used.